/**
复杂度：O(m); 

注：1和2配对，3和4配对，从1开始； 

若想在可行解中不想有x，则连一条边：x->x'; 

基本逻辑关系
x   1 (~x->x)
    0 (x->~x)
x&y 1 (~x->x)^(~y->y)
    0 (x->~y)^(y->~x)
x|y 1 (~x->y)^(~y->x)
    0 (x->~x)^(y->~y)
x^y 1 (x->~y)^(y->~x)^(~x->y)^(~y->x)
    0 (x->y)^(~y->~x)^(~x->~y)^(y->x)
**/
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <stack>
#include <map>
using namespace std;
const int maxm = 50010, maxn=16005;
struct A{ //表示邻接表的变量
    int nxt, v;
}edg[maxm],redg[maxm];
int head[maxn], rhead[maxn], E, rE;
//用来求连通分量的变量:连通集cnt从1开始；
int dfn[maxn], low[maxn], visitNum, cnt, stop;
bool instack[maxn];
int belong[maxn], stap[maxn];
//用来求拓扑排序的变量，hash用来判断是否存在；
int in[maxn], topi[maxn];
//bool hash[maxn][maxn];
//分组染色
int col[maxn];

int N; //结点个数为2*n;

inline void addedg(int u, int v){
    edg[E].v = v; edg[E].nxt = head[u];
    head[u] = E++;
    redg[rE].v = u; redg[rE].nxt = rhead[v];
    rhead[v] = rE++;
}
void tarjan(int i){
    int j, t;
    dfn[i] = low[i] = ++visitNum;
    instack[i] = 1;
    stap[++stop] = i;
    for (t=head[i]; t!=-1; t=edg[t].nxt){
        j = edg[t].v;
        if (!dfn[j]){
            tarjan(j);
            if (low[j]<low[i]) low[i] = low[j];
        }
        else if (instack[j] && dfn[j]<low[i])
            low[i] = dfn[j];
    }
    if (dfn[i]==low[i]){
        cnt++;
        while (1){
            j = stap[stop--];
            instack[j] = 0;
            belong[j] = cnt;
            if (j==i) break;
        }
    }
}
bool getscc() //判断相对的点是否在一个连通集里； Tajan
{
    memset (dfn, 0, sizeof(dfn));
    memset (instack, 0, sizeof(instack));
    stop=cnt=visitNum=0;
    for (int i=1; i<=N; i++){
        if (!dfn[i])
            tarjan(i);
    }
    for (int i=1; i<=N; i+=2){
        if (belong[i] == belong[i+1]) return false;
    }
    return true;
}
//对于缩点后的逆图，进行重新建图，因为要求反拓扑序； 
void build()
{
    memset (head, -1, sizeof(head)); E=0;
    memset (in, 0, sizeof(in));
    map<int, int> mp;
    //memset (hash, 0, sizeof(hash));
    
    int i, j, u, v;
    for (i=1; i<=N; i++){
        for (j=rhead[i]; j!=-1; j=redg[j].nxt){
            u = belong[i]; v = belong[redg[j].v];
            if (u!=v && !mp[u*(cnt+1)+v]){
                mp[u*(cnt+1)+v]=1;
                //hash[u][v] = 1;
                edg[E].v = v; edg[E].nxt = head[u];
                head[u] = E++;
                in[v]++; //表示入度，非0表示不是拓扑序的开头
            }
        }
    }
}
void toptical()
{
    stack<int> stk;
    int i, j, cur=0;
    for (i=1; i<=cnt; i++){//cnt代表进行缩点后的图，还剩下多少个点
        if (in[i]==0) stk.push(i);
    }
    while (!stk.empty()){
        j = stk.top(); stk.pop();
        topi[cur++] = j;
        for (i=head[j]; i!=-1; i=edg[i].nxt){
            int u = edg[i].v;
            in[u]--;
            if (in[u]==0) stk.push(u);
        }
    }
}
void col_dfs(int x)
{
    col[x]=2;
    int i, j;
    for (i=head[x]; i!=-1; i=edg[i].nxt){
        j=edg[i].v;
        if (!col[j]) col_dfs(j);
    }
}
void color()
{
    memset (col, 0, sizeof(col));
    int i, j, rj;
    for (i=0; i<cnt; i++){
        if (!col[topi[i]]){
            col[topi[i]] = 1;
            for (j=1; j<=N; j++){
                if (belong[j]==topi[i]){
                    if (j&1) rj=j+1;
                    else rj=j-1;
                    int v=belong[rj];
                    if (!col[v])
                        col_dfs(v);
                }
            }
        }
    }
}
void output()
{
    int i, j;
    for (i=1; i<=N; i++){
	//注：此处为输出可行解，若可行解的对立面，则为2：col[belong[i]]==2; 
        if (col[belong[i]]==1) printf ("%d\n", i);
    }
}
int main()
{
    freopen ("SPO.IN", "r", stdin);
    freopen ("SPO.OUT", "w", stdout);
    int n, m, a, b, ra, rb;
    while (scanf ("%d%d", &n, &m)!=EOF){
        N = n<<1;
        memset (head, -1, sizeof(head)); E=0; //建立邻接表之前的初始化
        memset (rhead, -1, sizeof(rhead)); rE=0;
        while (m--){
            scanf ("%d%d", &a, &b);
            if (a&1) ra = a+1;
            else ra = a-1;
            if (b&1) rb = b+1;
            else rb = b-1;
            addedg(a, rb); addedg(b, ra);
        }
	//以上是建图的过程； 
        if (!getscc())
            printf ("NIE\n");
        else{
            build();
            toptical();
            color();
            output();
        }
    }
    return 0;
}
